package A一周刷爆LeetCode.A基础班.H前缀树和贪心算法;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author wei.zhao
 * @description: 最大利润
 * @date 2022年03月25日 12:48
 */
public class Code05_IPO {

    public static int findMaximizedCapital(int[] costs, int[] profits, int k, int m) {
        int result = m;
        // 根据每个项目的花费，构建小根堆
        PriorityQueue<Project> costQueue = new PriorityQueue<>(Comparator.comparing(e -> e.c));
        for (int i = 0; i < costs.length; i++) {
            costQueue.add(new Project(costs[i], profits[i]));
        }
        // 已经解锁的项目，根据利润，构建大根堆
        PriorityQueue<Project> profitQueue = new PriorityQueue<>((a, b) -> b.p - a.p);
        for (int i = 0; i < k; i++) {
            //将解锁的项目丢入到大根堆中
            while (!costQueue.isEmpty() && costQueue.peek().c <= m) {
                profitQueue.add(costQueue.poll());
            }
            //弹出利润最大的项目，做
            if (!profitQueue.isEmpty()) {
                Project project = profitQueue.poll();
                result += project.p;
            } else {
                return result;
            }
        }
        return result;
    }

    public static class Project {
        //花费
        public int c;
        //利润
        public int p;

        public Project(int c, int p) {
            this.c = c;
            this.p = p;
        }
    }

}
